package lc20240605;

import java.util.*;

public class GeneSequence {
    public static void main(String[] args) {
        GeneSequence gene = new GeneSequence();
        int res = gene.minMutation("AACCGGTT", "AAACGGTA", new String[]{"AACCGGTA","AACCGCTA","AAACGGTA"});
        System.out.println(res);
    }

    public int minMutation(String startGene, String endGene, String[] bank) {
        //将基因库转换为集合
        Set<String> geneBank = new HashSet<>(Arrays.asList(bank));
        //如果目标不在基因库中返回-1
        if (!geneBank.contains(endGene)) {
            return -1;
        }

        //初始化队列和访问集合
        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        Set<String> visited = new HashSet<>();
        //将开始基因加入进来
        visited.add(startGene);

        //可供选择的基因字符
        char[] geneChars = {'A', 'C', 'G', 'T'};
        int mutations = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            System.out.println(size);
            System.out.println(queue.size());
            //这里要写size，当前层size
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(endGene)) {
                    return mutations;
                }
                for (int j = 0; j < cur.length(); j++) {
                    char[] curArray = cur.toCharArray();
                    char originalChar = curArray[j];
                    for (char geneChar : geneChars) {
                        if (geneChar == originalChar) {
                            continue;
                        }
                        curArray[j] = geneChar;
                        String newStr = new String(curArray);
                        if (geneBank.contains(newStr) && !visited.contains(newStr)) {
                            //在这个基础上进行变化
                            queue.offer(newStr);
                            visited.add(newStr);
                        }
                    }
                }
            }
            //一次只能改变一个字符
            mutations++;
        }
        return -1;
    }
//        List<String> list = new ArrayList<>();
//        for (int i = 0; i < startGene.length(); i++) {
//            StringBuilder str = new StringBuilder(startGene);
//            char c = str.charAt(i);
//            StringBuilder temp = new StringBuilder("ACGT");
//
//            if (c == 'A') {
//                temp.deleteCharAt(0);
//                for (int i1 = 0; i1 < temp.length(); i1++) {
//                    str.setCharAt(i, temp.charAt(i1));
//                    list.add(str.toString());
//                }
//            }
//            if (c == 'C') {
//                temp.deleteCharAt(1);
//                for (int i1 = 0; i1 < temp.length(); i1++) {
//                    str.setCharAt(i, temp.charAt(i1));
//                    list.add(str.toString());
//                }
//            }
//            if (c == 'G') {
//                temp.deleteCharAt(2);
//                for (int i1 = 0; i1 < temp.length(); i1++) {
//                    str.setCharAt(i, temp.charAt(i1));
//                    list.add(str.toString());
//                }
//            }
//            if (c == 'T') {
//                temp.deleteCharAt(3);
//                for (int i1 = 0; i1 < temp.length(); i1++) {
//                    str.setCharAt(i, temp.charAt(i1));
//                    list.add(str.toString());
//                }
//            }
//        }
//        System.out.println(list);
//        boolean flag=false;
//        for (String string : bank) {
//            if (list.contains(string)) {
//                flag=true;
//            }
//        }
//        if (!flag){
//            return -1;
//        }
//        return 0;
}
